COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00058 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a116.tex[106,phy] replacing A33.tex[106,phy] \today\hfill}
\font\rmn=cmr9

\bigskip

\line{\bf Algorithms\hfill}

\bigskip
Originally an {\it algorithm\/} was a rule for doing arithmetic using
Arabic numerals. The word comes from the name of Abu Ja'far Mu\d hammed 
ibn M\↑us\↑a al-Khw\↑arizm\↑\i, a ninth century Arabic mathematician
who wrote a famous textbook on arithmetic. We use the word now to mean
any set of rules for carrying out a (usually complex) series of actions
to achieve a goal. A~recipe, or the instructions for using a tape recorder,
are algorithms. Usually, what we call algorithms work with symbols and
require a sequence of actions and choices. If a process could be one by a fish or
a tree, we wouldn't usually call it an algorithm; if it requires a human,
a~machine, or a computer, we would. Algorithms are to thought what machines
are to objects: they are artifacts designed to do a specific task and do it
well, without requiring imagination or intuitive understanding.
Before the advent of the computer, huge teams of clerks calculated tables
of logarithms, trigonometric functions, and data for aiming artillery.
Probably few of them understood the reasons for the algorithms they used.
Now such tasks are usually done electronically. 

An algorithm may work on numbers, like the rules for long division and
for adding fractions. It may work on a written text, perhaps by checking
the spelling of each word with a dictionary. It may work on geometrical
figures, for example by drawing a circle through three given points.
It may also work on machines, nature, or people; there are algorithms
for mowing a lawn, driving someone to the airport, and baking a pie.
This book is about the design and use of algorithms. It concentrates on
algorithms to be performed by electronic computers, and written in a
specialized language called Pascal, but it is also about algorithms
done by hand or with a pocket calculator, and much of it carries over
to other languages for programming computers.

As an example of an algorithm, let's consider a rule for subtracting
$Y$ from~$X$ giving a result~$Z$, where all three numbers are whole
numbers with $X>Y>0$ (to keep the algorithm simple) and are written
using~3 as the number base (to keep it from being too familiar).
That is, $12201↓{(3)}$ represents a number that in the usual decimal
notation is $1\times 3↑4 +2\times 3↑3+2\times 3↑2+0\times 3↑1+1\times 3↑0
=81+54+18+0+1=154$. The algorithm uses two tables.
$$\vbox{\offinterlineskip%
\halign{\quad#\hfil&#\hfil&#\hfil&\vrule#&\strut\quad\hfil#\hfil%
&\quad\hfil#\hfil%
&\quad\hfil#\hfil\quad%
&#\hbox{\qquad\qquad}
&\quad#\hfil&#\hfil&#\hfil&\vrule#&\strut\quad\hfil#\hfil%
&\quad\hfil#\hfil%
&\quad\hfil#\hfil\quad\cr
&&\multispan5\hfil Table 1\hfil&&&&\multispan4\hfil Table 2\hfil\cr
\noalign{\smallskip}
&&$Y$&\omit&&&&&&&$Y$\cr
$X$&&&\omit&0&1&2&&$X$&&&\omit&0&1&2\cr
&&&\multispan4\hrulefill&&&&&\multispan4\hrulefill\cr
&\omit&\omit&height2pt&\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
&0&&&0&2B&1B&&&0&&&2B&1B&0B\cr
&1&&&1&0&2B&&&1&&&0&2B&1B\cr
&2&&&2&1&0&&&2&&&1&0&2B\cr
}}$$

\smallskip
\disleft 45pt:{Step 1:}:
Look up the rightmost digits of $X$ and $Y$ in Table~1. Write down the
digit from the table as the rightmost digit of~$Z$. Mark through the
rightmost digits of~$X$ and~$Y$. If there was a $B$~(borrow) in the
table entry, go to step~3; if not, go to step~2.

\smallskip
\disleft 45pt:{Step 2:}:
If $X$ and $Y$ are both used up, you are finished. Otherwise, look up the
rightmost remaining digits of $X$ and~$Y$ in Table~1, using a zero as
the digit of~$Y$ if $Y$ is used up. Write down the digit from the table
at the left end of~$Z$. Mark through the rightmost digits of~$X$ and~$Y$.
If there was a $B$ in the table, go to step~3; if not, go to step~2.

\smallskip
\disleft 45pt:{Step 3:}:
Just like step 2, except that Table 2 is used, not Table 1.

\medskip
Here is a record of the subtraction algorithm at work. Like frames from a
movie film, each line shows the state every changing part of the algorithm
was in at some moment.
$$\vcenter{\halign{#\hfil\qquad&\hfil#\qquad&\hfil#\qquad&\hfil#\qquad%
&\hfil#\hfil\cr
&$X$&$Y$&$Z$&Borrow?\cr
\noalign{\smallskip}
Initially&21012&121¬hing\cr
After Step 1&2101&12&1&No\cr
After Step 2&210&1&21&Yes\cr
After Step 3&21&gone&121&Yes\cr
After Step 3&2&gone&0121&No\cr
After Step 2&gone&gone&20121&No\cr
\noalign{\smallskip}
\multispan5\hfil Algorithm Movie \#1: Subtraction\hfil\cr
}}$$

Since
$$\vcenter{\offinterlineskip%
\halign{$\hfil#$&$\;\hfil#\hfil\;$&$\hfil#$\cr
\quad 21012↓{(3)}\quad&=&\quad 194\quad\cr
\noalign{\smallskip}
\quad -121↓{(3)}\quad&=&\quad -16\quad\cr
\noalign{\smallskip}
\hrulefill&&\hrulefill\cr
\noalign{\smallskip}
\quad 20121↓{(3)}\quad&=&\quad 178\quad\cr}}$$
the algorithm has given the right answer. Does it always work? You probably
can't say. Could you design a similar algorithm, say for long division?
Probably not. The requirement that an algorithm work correctly for each
of an infinite number of possible problems makes the algorithm easy to
use but hard to design and test.

When you learned to add, you already knew how to count, i.e., to get the
next larger number. When you add the hundreds digits of two numbers, you
remember whether there was a carry from the tens digits.
If there is a carry, you use your counting algorithm to get the next
number larger than the one in the addition table. You need the counting
algorithm to do a step in the addition algorithm. In the same way, you use
an addition algorithm as part of your multiplication algorithm. Commonly,
complex algorithms make use of simpler ones.
An algorithm used within another one is called a {\it subalgorithm}. Other
subalgorithms are used in arithmetic to line up decimal points and to decide
which of two numbers is larger.

{\rmn
{\narrower\smallskip\noindent
{\bf Drill.}
Add 7155024138594890803108327777777777777877777779993512657143437789599999996
23526 to 
8627954695744449562648152661407309746213833220414261069105435435435435435435
43543652560842425.
\smallskip}
}

{\rmn
{\narrower\smallskip\noindent
{\bf Drill.}
Which of these two numbers is greater,
$$85889230725886718372108085241585 \hbox{ or } 8588923075838671937210805241585\,?
\footnote\dag{The first one is; did you get it right?}$$
\smallskip}
}

{\rmn
{\narrower\smallskip\noindent
{\bf Drill.}
What is the next number after
$$768847474675311338864879999999999899999999999999999999999999999\,?$$
\smallskip}
}

What subalgorithms did you need to do these three drills?
You probably found you needed several to do things you can do unconsciously
on short numbers. Drills like these appear throughout this book to let you
check your understanding as you read.

The algorithms for arithmetic we learned in school only work for numbers
so short that we can temporarily memorize them. When we get to really large
numbers, the only way to get correct results is to make all the rules
explicit, including systems for keeping your place.

For example, to test whether $X>Y$, where $X$ and $Y$ are positive integers
that may be very long, one algorithm reads the numbers from right to left,
alternating between reading a digit of~$X$ and a digit of~$Y$.
This requires marking each digit that has been read. We assume neither
number starts with a zero. The algorithm keeps a tentative answer, which
becomes the final answer when the reading is finished.

\smallskip
\disleft 45pt:{Step 1:}:
Let the tentative answer be No. Go to Step 2.

\smallskip
\disleft 45pt:{Step 2:}:
Read and scratch the rightmost digits of $X$ and $Y$.
If the digits are equal, the tentative answer is left unchanged. If
they are unequal, the tentative answer becomes Yes or No depending
on whether or not the digit of~$X$ is the larger. If there is a digit
of~$X$, and none of~$Y$, the final answer is Yes; stop. If there is a
digit of~$Y$, and none of~$X$, the final answer is No; stop.
If both $X$ and $Y$ are exhausted, the tentative answer becomes the
final answer; stop. If not finished, repeat Step~2.

{\rmn
{\narrower\smallskip\noindent{\bf Drill.}
Modify the above algorithm so that it will work even if one or both
of the numbers $x$ and~$y$ start with one or more zeroes.
\smallskip}
}

{\rmn
{\narrower\smallskip\noindent{\bf Solution.} 
If you read a zero digit of one number, and there are no digits left
in the other, the tentative answer does not change; keep reading the number that
has not been exhausted.
\smallskip}
}

{\rmn
{\narrower\smallskip\noindent{\bf Drill.}
Design an algorithm to test whether $x>y$ by reading $x$ and~$y$ from left
to right.
\smallskip}
}

To find the next number after a given number, read the number from right to left,
writing down (from right to left) a digit of the answer for every digit of the
original number you read.  The process works in two stages, starting in Stage~1.

\smallskip
\disleft 45pt:
Stage 1:  If you are looking at a~9, write down a zero, and stay in Stage~1.
	  If you are looking at a digit other than~9, write down the next
	  larger digit, and proceed to Stage~2. If you are looking at a blank
	  space, write down a~1 and stop (this is to handle numbers like~999).

\smallskip
\disleft 45pt:
Stage 2:  If you are looking at a digit, copy it.  If you are looking at a blank
	  space, stop.

{\rmn
{\narrower\smallskip\noindent{\bf Drill.}
Write out in full the algorithm you use to perform long division.
\smallskip}
}

There is a traditional algorithm [Knuth, {\sl Seminumerical Algorithms\/},
{\bf 2}, pg.~400]
used by Russian peasants to multiply numbers
of several digits, based on subalgorithms for
doubling, halving, and addition.  To see why it
works, let's first look at a particular multiplication problem.

How much is $38\times 45$?  Since $38 = 19\times 2$, 
$38\times 45 = 19\times 2\times 45 = 19\times 90$.  
That's 90 more than $18\times 90$, so
$$19\times 90 = 18\times 90 + 90 = 9\times 2\times 90 + 90 = 9\times 180 + 90
\bblackslug$$
Since $9\times 180$ is 180 more than $8\times 180$,
$$\eqalign{9\times 180 + 90&= 8\times 180 + 180 + 90 = 8\times 180 + 270\cr
&= 4\times 2\times 180 + 270 = 4\times 360 + 270\cr
4\times 360 + 270&= 2\times 2\times 360 + 270 
= 2\times 720 + 270 = 1440 + 270 = 1710
\bblackslug\cr}$$

Now that the method is clear, the process can be shortened to filling out a table.
In each row, we have two numbers we want to multiply, and another number to be
added on to the result.  For the calculation above, here is the table:
$$\vcenter{\halign{$\rt{#}$\quad&$\rt{#}$\quad&$\rt{#}$\cr
A&B&C\cr
\noalign{\smallskip}
38&45&0\cr
19&90&0\cr
18&90&90\cr
9&180&90\cr
8&180&270\cr
4&360&270\cr
2&720&270\cr
1&1440&270\cr
0&1440&1710\cr}}$$
\centerline{Algorithm Movie: Russian Peasant Multiplication}

\medskip
Here is an explicit algorithm for making the table.

\smallskip
\disleft 25pt:
(1):The first row across contains, in columns $A$ and~$B$, the numbers we want to
    multiply, 38 and 45 in this example, and in column $C$ a zero.

\disleft 25pt:
(2):If $A=0$ in the bottom row of the table, we are finished; the entry in 
column~$C$ is the answer.  Otherwise we need to make another row.  

\disleft 25pt:
(3):If, in the bottom row, $A$ is even, we make the next row by halving the number
in column~$A$, doubling the number in column~$B$, and copying 
in column~$C$ the number above it.

\disleft 25pt:
(4):If, in the bottom row, $A$ is odd, 
we make the next row by subtracting one from
the number in column~$A$, copying the number in column~$B$, 
and adding the number from column~$B$ to the number in column~$C$.

\smallskip
Every row in the table stands for a formula; the fifth row, above, stands for
$8\times 180 + 270$.  
People who work with algorithms find ways to represent entities
that are not just numbers by sequences of numbers; this allows using computers
that only handle numbers to solve problems that involve not only numbers, but
pictures, words, formulas, logic, and myriad other entries.

For example, a triangle can be represented by the coordinates $x↓1$, $y↓1$,
$x↓2$, $y↓2$, $x↓3$, $y↓3$ of its vertices. In this representation, one can
find the area by the formula $x↓1(y↓2-y↓3)+x↓2(y↓3-y↓1)+x↓3(y↓1-y↓2)$.
One can test whether the angle at $(x↓1,y↓1)$ is a right angle by testing
whether $(x↓2-x↓1)(x↓3-x↓1)+(y↓2-y↓1)(y↓3-y↓1)=0$. 
Most other geometric properties of the triangle can be restated as properties
of the list of numbers that represents it.

Going back to the Russian peasant multiplication algorithm,
the successive rows represent different formulas, but each formula stands for
the same number as the one before it, so they all stand for the same number.
We get from the problem to the solution by picking a first line that is easy
to construct from the problem, and getting to a last line from which it is easy
to construct the solution.  In between, we need steps that are easy to carry
out, that progress toward an acceptable last line, and that change the question
without changing the answer.  That is, we go from ``What is 
$8\times 180 + 270$?'' to
``What is $4\times 360 + 270$?'' without changing the answer, 1710.

A good algorithm is like good government; it involves both stability and progress.
Progress in solving a problem comes from changing it into a simpler problem;
stability comes from assuring that each new problem has the same answer as the one
it grew from.  In the Russian peasant multiplication algorithm, progress is
guaranteed because columnn~$A$ gets closer to zero at every step; it can't go on
forever, since there are only a limited number of possible values $A$ can have,
once we know the first value.  Stability is guaranteed because in each row, the
formula $A\times B+C$ has the same value.

{\rmn
{\narrower\smallskip\noindent
{\bf Drill.}  Find an algorithm for halving.  (Notice that to use it in the 
Russian peasant
algorithm, you must remember your place in the main algorithm while you
carry out the subalgorithm.)
\smallskip}
}

To reduce fractions to their simplest forms we use an algorithm that gives
the greatest common divisor of the numerator and denominator. Here is the
result of applying a simplified form of the standard algorithm to 75/195:
$$\vcenter{\halign{\hfil$#$\qquad&\hfil$#$\cr
x\hfil&y\hfil\cr
\noalign{\smallskip}
195&75\cr
120&75\cr
45&75\cr
75&45\cr
30&45\cr
45&30\cr
15&30\cr
30&15\cr
15&15\cr
0&15\cr
15&0\cr}}$$

In the first row, $x$ and $y$ are the two numbers whose greatest common
divisor (GCD) we want. Then: If $y=0$ in the bottom row, the answer is~$x$;
stop. If $x≥y$ in the bottom row, make a new row with $x-y$ in column~$x$,
copying the number in column~$y$.
Otherwise (i.e., $x<y$), make a new row with $x$ and~$y$ exchanged.

As we watch the algorithm work on the example, we notice that the final
answer, 15, is always a divisor of both $x$ and~$y$. Other divisors,
like~10, divide $x$ sometimes, $y$~sometimes, but never both.
In the first row, the divisors of~$x$ are 1, 3, 5, 13, 15, 39, 65, and~75.
In the second row, the divisors of~$x$ have become 
1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120. New divisors
of~$x$ like 2 and~4 have entered, but none are divisors of~$y$. Divisors
like~13 have departed; again none divide~$y$. This is the key to understanding
the algorithm: the set of common divisors of $x$ and~$y$, which in this
example is $\{1,3,5,15\}$, never changes.

{\rmn
{\narrower\smallskip\noindent
{\bf Drill.}
If $d$ is a divisor of $x$ and~$y$, then it divides $x-y$ and~$y$, and
vice versa.
\smallskip}
}

\noindent
The principle of stability for this algorithm is that each row has the
same common divisors as the one above it. There are several ways to state
a principle of progress. One is that $2y+x$ decreases at every step,
while staying positive.

An algorithm need not work with numbers. Here is an algorithm to find a word in
the dictionary:

{\narrower\smallskip\noindent
Insert your left index finger between pages at the beginning of the dictionary,
and your right index finger at the end.  Open the dictionary somewhere between
your fingers (If you can't, you've already found the right page).  Look at the
word in the top left corner of the newly opened page.  If it is alphabetically
earlier than the word you are looking for, move your left index finger into the
new opening; otherwise, move your right index finger there.  
\smallskip}

\noindent
Here is a record of
looking up ``scutage'' in the Shorter Oxford English Dictionary.

%\vfill\eject

$$\vcenter{\halign{\hfil#\hfil\quad&#\hfil\qquad%
&\hfil#\hfil\quad&#\hfil\qquad%
&\hfil#\hfil\quad&#\hfil\cr
\multispan2\qquad\quad Left finger\hfil&
\multispan2\qquad\quad Right finger\hfil&
\multispan2\qquad\quad New opening\hfil\cr
\noalign{\smallskip}
page number&\quad word&page number&\quad word&page number&\quad word\cr
\noalign{\smallskip}
\phantom{127}1&A&2475&Zygin&1278&Monthly\cr
1278&Monthly&2475&Zygin&1822&Sea-horse\cr
1278&Monthly&1822&Sea-horse&1542&Pomatum\cr
1542&Pomatum&1822&Sea-horse&1682&Redowa\cr
1682&Redowa&l822&Sea-horse&1730&Revolutionary\cr
1730&Revolutionary&1822&Sea-horse&1780&Sailyard\cr
1780&Sailyard&1822&Sea-horse&1800&Scantity\cr
1800&Scantity&1822&Sea-horse&1810&Scorer\cr
1810&Scorer&1822&Sea-horse&1816&Scriptural\cr
1816&Scriptural&1822&Sea-horse&1820&Sea\cr
1816&Sciptural&1822&Sea-horse&1818&Sculptile\cr
1818&Sculptile&1820&Sea&(none)\cr}}$$
The principle of stability is that the word I'm looking for stays between my
fingers.  The principle of progress is that the number of pages between my
fingers gets smaller.

Many algorithms embodied in computer programs are not reliable; when used on
certain data they give wrong answers, or they continue calculating until
someone intervenes.  The way to make an algorithm reliable is to design it
around a principle of stability and a principle of progress.  If you can't
formulate a principle of stability for an algorithm, it is likely to change
the problem it is solving as it goes along, and end up computing the right
answer to the wrong problem.  If you can't formulate a principle of progress,
the algorithm is likely to run forever on some data.  As the Russian peasant
multiplication and greatest common divisor algorithms show, it becomes much
easier to understand a new algorithm when its principle of stability (technically
known as an {\sl invariant\/}) is presented with it.

\smallskip
Computers are machines to carry out algorithms; to be useful, they must be
able to execute long, complicated algorithms on numerous data quickly  and
reliably.  A computer  carries out  an algorithm  as expressed  in one  of
several precisely  defined  languages  for  that  computer.  An  algorithm
expressed in a  language executable by  some actual computer  is called  a
{\sl program\/}.

Programming,  the  design  of  programs, consists  of  two  parts,   often
interwoven:  the  design of  an  algorithm to  solve  a problem,  and  the
expression of that algorithm as a program within the limited notations  of
a particular computer language.  To learn to program,  you must learn  and
use some particular programming language, just as music is learned on some
particular instrument.   The  core  of learning  to  program,  though,  is
learning to design algorithms.

Algorithms meant to be performed by humans can be expressed in any way that
the humans can understand.  Algorithms meant to be performed by computers
must be expressed in a language computers can interpret.  Most computers
are designed to carry out only algorithms written in a very crude notation
(``machine language'') that most humans find unsatisfactory as a language in
which to express algorithms.  We meet the needs of both the human algorithm
designer and the computer interpreting the algorithm by providing a
translation;  programmers write algorithms in a language designed for
convenience and expressiveness, the algorithm is translated (by another,
pre-existing computer program) into machine language, and the machine
language version of the algorithm is performed by the computer.  The
programmer need not know anything about the machine language; 
in fact, little programming is done in machine language.

In this book, we use the Pascal programming language. It is popular with users
of small to  medium-sized computers  (``micros'' and  ``minis''), and  has
become  a  common  language  for  communication  of  algorithms  in print.
There are many other languages, some of them more suitable than Pascal for
particular types of problems: PL-I and COBOL for business applications,
LISP for symbolic computation, SIMULA for simulation, and so on. Even
if you will eventually use another language, it is reasonable to start
programming in Pascal, which is versatile without being excessively complicated.
Most of what you learn will carry over to other languages, and learning
the fundamentals of a second or third programming language requires only
a day or~so.

Pascal is a language for writing algorithms, in a mixture of English and
mathematical notation.  Programs written in Pascal can be translated, by
other programs called {\sl compilers\/} or {\sl translators\/}, into the machine
languages of most popular computers.  
The International Standards Organization (ISO) has formulated a definition
of Pascal, called Standard Pascal, which is widely accepted; normally,
programs in Standard Pascal can be expected to work with all translators of
recent design.  
Because Pascal is standardized,
programs written in Pascal can be shared among the users of diverse
computers, and can continue to be used without change when obsolete
computers are replaced by newer ones.
Most Pascal translators accept programs in Pascal extended by notations to
make more efficient use of facilities peculiar to a particular computer.
This text uses Standard Pascal almost exclusively;
departures to use computer capabilities not expressible in Pascal are
explicitly labeled non-standard.

So, you will learn Pascal, and, with labor and attention, how to design an
algorithm systematically and correctly. You won't learn all of Pascal from
this text. This is no  oversight; parts of Pascal  are largely of use  to
more experienced programmers,  and parts are  of doubtful usefulness.   If
you have trouble  with the problems,  it won't be  because you don't  know
Pascal well enough.

My goal is to teach you to design, systematically and correctly, computer
programs more complicated  than anything  else you have  ever designed  in
your life, even though
programs are so sensitive to  error that a single typing error
will probably  make the  program incorrect.   I~want you to learn  to
program in such a way that your first drafts of programs will contain  few
errors other  than  slips  of the  pen,  and  that your  programs  can  be
systematically tested and corrected (``debugged'').

Programming without  standards  of  quality  is  easy.  
Serious programming is engineering, and is hard.
Programming  is  a
difficult discipline if a program must be utterly trustworthy
on all valid data; if it must  detect and report all invalid data;  if
its results must be intelligible  and unambiguous; if other  programmers
must be  able to  adapt the  program to  other languages,  computers,  and
problems than those for which it  was originally designed, long after  the
original programmer has vanished.

The text is interlaced  with Rules of Good Programming  Practice.
These are only a small subset of the 927 (or was it 928?) eternal  truths
[Sheldon B. Kopp, {\sl If You Meet the Buddha on the Road, Kill Him\/},
pg.~165--167],
but they are very useful,  and should adhere to them or
(since they have exceptions) have a good reason.

[Omit next three paragraphs from book.]

We also  expect you  to take  responsibility for  yourself
[{\sl ibidem\/}, Truths 34 and 35].  The  computer
center can be a difficult environment. The computer may fail for a day  at
a time.  Lines to  use the computer may  be hours long at  the end of  the
term.  Assignments may be more  difficult than intended. We expect  you
to begin projects as  early as possible; if  the computer fails six  hours
before a program is due,  that is your problem. We  expect you to use  the
often overloaded  computer system  in  a way  considerate to  your  fellow
students; in particular, when you no  longer are sure what you are  doing,
get off the computer and let someone else use it.  Also, delete any  files
you no longer need, to release storage capacity for other users.  We expect
your programs to work for all valid data, and not just for the test  cases
you run; to design a program deliberately that only works for the data  on
which it is tested will be considered  cheating. We expect you to plan  to
spend fifteen hours a week on  this course (the university guideline for  a
5-unit course) including class and computer time; you will find the course
unsuitable as part of an 18-unit program.

We expect  you,  as the  assignments  become more  difficult,  to  include
adequate explanations  of how  your program  works. Let  the  hard-pressed
grader, who perhaps  just took the  course the previous  quarter, know  in
outline what your methods are. And if your native language is English,  we
would appreciate a demonstration of the fact. We expect you to respect the
privacy of other people's  computer files; the fact  that someone has  not
fully protected his files does not give you the right to read them.

Okay, we've told you the worst. On the good side, the teaching assistants,
consultants, and professor are there to  help out. Not by doing your  work
for you, but by serving as models of how to think about programming.  Most
of the  time, the  computer  center is  a  friendly environment.  The
computer itself is  the most versatile  tool you will  ever use. You  have
signed up to vastly  extend your powers to  use and create information.  I
think you will be glad you did.


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft March 28, 1984; 
revised: February 13, 1987.
%subsequently revised.


\bye